package aloge;

import java.util.*;

/**
 * 单源最短路径求值
 */
public class ShortGrap {



    public static void main(String[] args) {
        ShortGrap shortGrap = new ShortGrap();
        int shortedWay = shortGrap.findShortedWay(new int[][]{
                new int[]{1,2},
                new int[]{3},
                new int[]{5},
                new int[]{4},
                new int[]{5},
                new int[0]
        });
        System.out.println(shortedWay);
    }

    public int findShortedWay(int[][] edges) {
        int n = edges.length;
        int[] d = new int[n];
        // 到各个路径最短的前驱节点
        int[] prev = new int[n];
        Arrays.fill(prev, -1);
        Deque<Integer> queue = new LinkedList<>();
        queue.addFirst(0);
        // 广度优先
        while (!queue.isEmpty()) {
            Integer last = queue.pollLast();
            for (int i : edges[last]) {
                // 如果d[i] 是0
                if (d[i] == 0) {
                    // 说明没添加过
                    d[i] = d[last] + 1;
                    prev[i] = last;
                    queue.addFirst(i);
                    if (i == n - 1) {
                        return d[i];
                    }
                }
            }
            System.out.println(Arrays.toString(d));
        }
        return d[n-1];
    }

}
